/*
49. 字母异位词分组

给你一个字符串数组，请你将 字母异位词 组合在一起。可以按任意顺序返回结果列表。

 
示例 1:

输入: strs = ["eat", "tea", "tan", "ate", "nat", "bat"]

输出: [["bat"],["nat","tan"],["ate","eat","tea"]]

解释：

在 strs 中没有字符串可以通过重新排列来形成 "bat"。
字符串 "nat" 和 "tan" 是字母异位词，因为它们可以重新排列以形成彼此。
字符串 "ate" ，"eat" 和 "tea" 是字母异位词，因为它们可以重新排列以形成彼此。
示例 2:

输入: strs = [""]

输出: [[""]]

示例 3:

输入: strs = ["a"]

输出: [["a"]]

 
提示：

1 <= strs.length <= 104
0 <= strs[i].length <= 100
strs[i] 仅包含小写字母
*/


class Solution {
    public List<List<String>> groupAnagrams(String[] strs) {
        // 创建一个 List 类用于存储每一组字母异位词
        List<List<String>> allArr = new ArrayList<>();

        // 将 strs 中的所有元素都根据 ASCII 排序
        // 循环遍历每一个字符串的每一个字符，并将字符串的每一个字符值都开方最后相加
        //    将每一个字符串对应的结果值与字符串对应的数组下标一起映射存储
        Map<String, String> map = new HashMap<>();

        // 分类集合元素
        // 循环 strs 字符串
        for (int i = 0; i < strs.length; i++) {
            // 循环字符串，放置于临时变量 byteString 中
            byte[] bytes = strs[i].getBytes();
            Arrays.sort(bytes);

            String byteString = Arrays.toString(bytes);

            // 检测映射中是否已经存在对应的 key
            String mapValue = map.get(byteString);

            // 判断 mapValue key 对应的 value 是否存在
            if (mapValue == null){
                // 如果不存在则直接添加
                map.put(byteString, String.valueOf(i));
            } else {
                // 如果已经存在则修改 value,将新的 value 添加到原先 value 的后面，使用逗号隔开
                String newValue = mapValue + "," + i;
                map.replace(byteString, newValue);
            }
        }

        // 重组集合
        // 循环map，相同 key 的 value 通过 strs[value] 存入集合，最后放入 allArr 中
        System.out.println(map);
        Set<String> keySet = map.keySet();

        // 循环每个 key
        for (String i : keySet) {
            String value = map.get(i);
            // 将每个 value 根据逗号隔开获得数组
            String[] split = value.split(",");

            List<String> arr = new ArrayList<>();
            // 将数组对应的 strs 数据存入一个集合，然后将这个集合存入 allArr
            for (String s : split) {
                arr.add(strs[Integer.valueOf(s)]);
            }
            allArr.add(arr);
        }

        return allArr;
    }
}